<?xml version="1.0" encoding='UTF-8' ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <meta name="generator" content="SciTE" />
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <meta name="keywords" content="gap buffer, split vector, mutable string, python" />
    <meta name="Date.Modified" content="20070326" />
    <title>gapbuffer</title>
</head>
<body>
<h3>gapbuffer Python module</h3>
<p>This module implements a gap buffer for Python.
A gap buffer is a data structure often used in text editors since it allows modifications
to be efficient.</p>
<p>For a description of gap buffers see
<a href="http://www.cs.cmu.edu/~wjh/papers/byte.html">Data Structures in a Bit-Mapped Text
Editor</a>, <i>Wilfred J. Hanson</i>, Byte January 1987
</p>
<p>The item type for the gap buffer may be character, Unicode character, or integer
and is determined from the type of the initial value argument to the constructor with a
list interpreted as integer:</p>
<code>
>>> from gapbuffer import GapBuffer<br />
>>> print GapBuffer("The life of Brian")<br />
The life of Brian<br />
>>> print GapBuffer(u"Mr Creosote")<br />
Mr Creosote<br />
>>> print GapBuffer([1,2,3])<br />
GapBuffer('i') [1, 2, 3]<br />
</code>

<p>GapBuffer implements Python's sequence protocol:</p>
<code>
>>> movie = GapBuffer("The life of Brian")<br />
>>> movie[:] = "The meaning - with Life"; print movie<br />
The meaning - with Life<br />
>>> del movie[12:14]; print movie<br />
The meaning with Life<br />
>>> movie[4] = "M"; print movie<br />
The Meaning with Life<br />
>>> movie[12:16] = "of"; print movie<br />
The Meaning of Life<br />
>>> print movie[0:3]<br />
The<br />
>>> print len(movie)<br />
19<br />
</code>

<p>GapBuffer has insert and extend methods similar to Python lists:</p>
<code>
>>> movie.insert(0, "\'")<br />
>>> movie.extend("\'!")<br />
>>> print movie<br />
'The Meaning of Life'!<br />
</code>

<p>Portions can be retrieved as strings directly rather than by a slice and conversion
to avoid copying twice with retrieve(start, length):</p>
<code>
>>> print movie.retrieve(5,7)<br />
Meaning<br />
</code>

<p>A GapBuffer will not release memory unless asked:</p>
<code>
>>> print movie.size<br />
25<br />
>>> movie[:] = "ab"; print movie.size<br />
25<br />
>>> movie.slim(); print movie.size<br />
8<br />
</code>

<p>The values of a segment may be added to with increment(start, length, value).
This is useful for maintaining the starting position of every line in a document, for example.</p>
<code>
>>> positions = GapBuffer([100, 140, 220, 280])<br />
>>> positions.increment(1,3,-7)<br />
>>> print positions<br />
GapBuffer('i') [100, 133, 213, 273]<br />
</code>

<p>The buffer protocol is implemented which allows use with features such as regular expression
searches and writing to file:</p>
<code>
>>> import re<br />
>>> movie = GapBuffer(u"The life of Brian")<br />
>>> print movie<br />
The life of Brian<br />
>>> r = re.compile("B[a-z]+", re.M)<br />
>>> where = r.search(movie)<br />
>>> print where.group(0)<br />
Brian<br />
</code>

<h3>Issues</h3>
<p>Despite using the version number 1.0, the API is not stable and may change.
More item types could be implemented, possibly all of those available from the array module
with a typecode keyword parameter to the constructor specifying the item type.
Possibly use different names rather than a typecode: CharDoc, UnicodeDoc.</p>
<p>The code is too messy with detailed knowledge of the data structure spread throughout the code.
This should be regularised as should be the consumption of arguments so it is easier to add methods
and item types.</p>
<h3>Download</h3>
<p>The <a href="http://www.scintilla.org/gapbuffer-1.0.zip">source code</a> can be downloaded and
built using normal Python distutils:<br />
<code>python setup.py build install</code></p>
<p>There are <a href="http://www.scintilla.org/gapbuffer-1.0.win32-py2.5.exe">
Windows binaries</a> for Python 2.5.</p>
<p><a href="http://www.scintilla.org/unitTests.py">Unit tests for gapbuffer</a></p>
<p><a href="http://www.scintilla.org/svdemonstration.py">Demonstration code</a></p>
<h3>License</h3>
<p>Your choice of Public Domain or MIT.</p>
<h3>Discussion</h3>
<p>Since this is a small simple module there will not be a mailing list. The news group comp.lang.python is probably the
best place to talk about gapbuffer. Do not send messages about gapbuffer to my personal email address.</p>
</body>
</html>
